/*
 * Copyright (c) 2015, EURECOM (www.eurecom.fr)
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * The views and conclusions contained in the software and documentation are those
 * of the authors and should not be interpreted as representing official policies,
 * either expressed or implied, of the FreeBSD Project.
 */

#include "lfds611_queue_internal.h"/****************************************************************************/intlfds611_queue_enqueue (  struct lfds611_queue_state *qs,  void *user_data) {  LFDS611_ALIGN (LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element    *qe[LFDS611_QUEUE_PAC_SIZE];  assert (qs != NULL); // TRD : user_data can be NULL  lfds611_queue_internal_new_element_from_freelist (qs, qe, user_data);  if (qe[LFDS611_QUEUE_POINTER] == NULL)    return (0);  lfds611_queue_internal_queue (qs, qe);  return (1);}/****************************************************************************/intlfds611_queue_guaranteed_enqueue (  struct lfds611_queue_state *qs,  void *user_data) {  LFDS611_ALIGN (LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element    *qe[LFDS611_QUEUE_PAC_SIZE];  assert (qs != NULL);  // TRD : user_data can be NULL  lfds611_queue_internal_guaranteed_new_element_from_freelist (qs, qe, user_data);  if (qe[LFDS611_QUEUE_POINTER] == NULL)    return (0);  lfds611_queue_internal_queue (qs, qe);  return (1);}/****************************************************************************/voidlfds611_queue_internal_queue (  struct lfds611_queue_state *qs,  struct lfds611_queue_element *qe[LFDS611_QUEUE_PAC_SIZE]) {  LFDS611_ALIGN (LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element    *enqueue[LFDS611_QUEUE_PAC_SIZE],    *next[LFDS611_QUEUE_PAC_SIZE];  unsigned char  cas_result = 0;  assert (qs != NULL);  assert (qe != NULL);  // TRD : the DCAS operation issues a read and write barrier, so we don't need a read barrier in the do() loop  LFDS611_BARRIER_LOAD;  do {    enqueue[LFDS611_QUEUE_POINTER] = qs->enqueue[LFDS611_QUEUE_POINTER];    enqueue[LFDS611_QUEUE_COUNTER] = qs->enqueue[LFDS611_QUEUE_COUNTER];    next[LFDS611_QUEUE_POINTER] = enqueue[LFDS611_QUEUE_POINTER]->next[LFDS611_QUEUE_POINTER];    next[LFDS611_QUEUE_COUNTER] = enqueue[LFDS611_QUEUE_POINTER]->next[LFDS611_QUEUE_COUNTER];    /*       TRD : this if() ensures that the next we read, just above,       really is from qs->enqueue (which we copied into enqueue)    */    LFDS611_BARRIER_LOAD;    if (qs->enqueue[LFDS611_QUEUE_POINTER] == enqueue[LFDS611_QUEUE_POINTER] and qs->enqueue[LFDS611_QUEUE_COUNTER] == enqueue[LFDS611_QUEUE_COUNTER]) {      if (next[LFDS611_QUEUE_POINTER] == NULL) {        qe[LFDS611_QUEUE_COUNTER] = next[LFDS611_QUEUE_COUNTER] + 1;        cas_result = lfds611_abstraction_dcas ((volatile lfds611_atom_t *)enqueue[LFDS611_QUEUE_POINTER]->next, (lfds611_atom_t *) qe, (lfds611_atom_t *) next);      } else {        next[LFDS611_QUEUE_COUNTER] = enqueue[LFDS611_QUEUE_COUNTER] + 1;        lfds611_abstraction_dcas ((volatile lfds611_atom_t *)qs->enqueue, (lfds611_atom_t *) next, (lfds611_atom_t *) enqueue);      }    }  } while (cas_result == 0);  qe[LFDS611_QUEUE_COUNTER] = enqueue[LFDS611_QUEUE_COUNTER] + 1;  lfds611_abstraction_dcas ((volatile lfds611_atom_t *)qs->enqueue, (lfds611_atom_t *) qe, (lfds611_atom_t *) enqueue);  return;}/****************************************************************************/intlfds611_queue_dequeue (  struct lfds611_queue_state *qs,  void **user_data) {  LFDS611_ALIGN (LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element    *enqueue[LFDS611_QUEUE_PAC_SIZE],    *dequeue[LFDS611_QUEUE_PAC_SIZE],    *next[LFDS611_QUEUE_PAC_SIZE];  unsigned char  cas_result = 0;  int  rv = 1,  state = LFDS611_QUEUE_STATE_UNKNOWN,  finished_flag = LOWERED;  assert (qs != NULL);  assert (user_data != NULL);  // TRD : the DCAS operation issues a read and write barrier, so we don't need a read barrier in the do() loop  LFDS611_BARRIER_LOAD;  do {    dequeue[LFDS611_QUEUE_POINTER] = qs->dequeue[LFDS611_QUEUE_POINTER];    dequeue[LFDS611_QUEUE_COUNTER] = qs->dequeue[LFDS611_QUEUE_COUNTER];    enqueue[LFDS611_QUEUE_POINTER] = qs->enqueue[LFDS611_QUEUE_POINTER];    enqueue[LFDS611_QUEUE_COUNTER] = qs->enqueue[LFDS611_QUEUE_COUNTER];    next[LFDS611_QUEUE_POINTER] = dequeue[LFDS611_QUEUE_POINTER]->next[LFDS611_QUEUE_POINTER];    next[LFDS611_QUEUE_COUNTER] = dequeue[LFDS611_QUEUE_POINTER]->next[LFDS611_QUEUE_COUNTER];    /*       TRD : confirm that dequeue didn't move between reading it       and reading its next pointer    */    LFDS611_BARRIER_LOAD;    if (dequeue[LFDS611_QUEUE_POINTER] == qs->dequeue[LFDS611_QUEUE_POINTER] and dequeue[LFDS611_QUEUE_COUNTER] == qs->dequeue[LFDS611_QUEUE_COUNTER]) {      if (enqueue[LFDS611_QUEUE_POINTER] == dequeue[LFDS611_QUEUE_POINTER] and next[LFDS611_QUEUE_POINTER] == NULL)        state = LFDS611_QUEUE_STATE_EMPTY;      if (enqueue[LFDS611_QUEUE_POINTER] == dequeue[LFDS611_QUEUE_POINTER] and next[LFDS611_QUEUE_POINTER] != NULL)        state = LFDS611_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE;      if (enqueue[LFDS611_QUEUE_POINTER] != dequeue[LFDS611_QUEUE_POINTER])        state = LFDS611_QUEUE_STATE_ATTEMPT_DELFDS611_QUEUE;      switch (state) {        case LFDS611_QUEUE_STATE_EMPTY:          *user_data = NULL;          rv = 0;          finished_flag = RAISED;          break;        case LFDS611_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE:          next[LFDS611_QUEUE_COUNTER] = enqueue[LFDS611_QUEUE_COUNTER] + 1;          lfds611_abstraction_dcas ((volatile lfds611_atom_t *)qs->enqueue, (lfds611_atom_t *) next, (lfds611_atom_t *) enqueue);          break;        case LFDS611_QUEUE_STATE_ATTEMPT_DELFDS611_QUEUE:          *user_data = next[LFDS611_QUEUE_POINTER]->user_data;          next[LFDS611_QUEUE_COUNTER] = dequeue[LFDS611_QUEUE_COUNTER] + 1;          cas_result = lfds611_abstraction_dcas ((volatile lfds611_atom_t *)qs->dequeue, (lfds611_atom_t *) next, (lfds611_atom_t *) dequeue);          if (cas_result == 1)            finished_flag = RAISED;          break;      }    }  } while (finished_flag == LOWERED);  if (cas_result == 1)    lfds611_freelist_push (qs->fs, dequeue[LFDS611_QUEUE_POINTER]->fe);  return (rv);}
